// 求二叉树的最大、最小深度
public class Code04_DepthOfBinaryTree {
    // 不提交这个类
    // TreeNode类用于表示二叉树的节点
    // 其中val表示节点的值，left和right分别表示左子节点和右子节点
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    // 测试链接 : https://leetcode.cn/problems/maximum-depth-of-binary-tree/
    // 计算二叉树的最大深度
    public static int maxDepth(TreeNode root) {
        // 如果根节点为null，说明二叉树为空，空树的深度为0
        if (root == null) {
            return 0;
        } else {
            // 递归计算左子树的最大深度
            int leftDepth = maxDepth(root.left);
            // 递归计算右子树的最大深度
            int rightDepth = maxDepth(root.right);
            // 二叉树的最大深度为左子树和右子树最大深度中的较大值再加1
            // 因为根节点本身也算一层
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }

    // 测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree/
    // 计算二叉树的最小深度
    public int minDepth(TreeNode root) {
        // 如果根节点为null，说明二叉树为空，空树的最小深度为0
        if (root == null) {
            return 0;
        }
        // 如果根节点的左子节点和右子节点都为null，说明当前节点是叶节点
        // 叶节点的最小深度为1
        if (root.left == null && root.right == null) {
            return 1;
        }
        int ldeep = Integer.MAX_VALUE;
        int rdeep = Integer.MAX_VALUE;
        // 如果左子节点不为null，递归计算左子树的最小深度
        if (root.left!= null) {
            ldeep = minDepth(root.left);
        }
        // 如果右子节点不为null，递归计算右子树的最小深度
        if (root.right!= null) {
            rdeep = minDepth(root.right);
        }
        // 二叉树的最小深度为左子树和右子树最小深度中的较小值再加1
        // 因为根节点本身也算一层
        return Math.min(ldeep, rdeep) + 1;
    }
}